#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <type_traits>
#include <vector>

class Solution {
 public:
  int searchInsert(std::vector<int> &nums, int target)
  {
    int l = 0, r = nums.size() - 1;

    while (l <= r)
    {
      int middle = l + ((r - l) / 2);
      if (target > nums[middle])
      {
        l = middle + 1;
      } else if (target < nums[middle])
      {
        r = middle - 1;
      } else
      {
        return middle;
      }
    }
    return l;
  }
};

int main(int argc, char *argv[])
{
  Solution s;
  std::vector<int> nums{1, 2, 4};
  std::cout << s.searchInsert(nums, 3);
  return 0;
}
